P3503 [POI2010]KLO-Blocks

发布于 2020-10-14 | 分类于单调栈/单调队列 | 2分钟 | 363字数 | 浏览量：

首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 $k$ 。

进一步可以发现这是一个充要条件。因为大于 $k$ 的数一定能填补到小于 $k$ 的数。

记一个合法的区间为 $[l,r]$ ， $sum$ 为 $a$ 的前缀和。

sum[r]-sum[l-1] \ge k \times (r-l+1)

sum[r]- k \times r \ge sum[l-1] - k \times (l-1)

记 $s_i=sum[i]-k \times i$

则有 $s_r-s_{l-1} \ge 0$

我们可以 $\Theta(n)$ 处理出 $s$ ，然后就可以用单调栈求解了。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1000000;
int n , m , k , a[ MAXN + 5 ] , Top , Stk[ MAXN + 5 ]; 
long long sum[ MAXN + 5 ];

int main( ) {
//  freopen("blocks.in","r",stdin);
//  freopen("blocks.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	while( m -- ) {
		scanf("%d",&k);
        for( int i = 1 ; i <= n ; i ++ )
            sum[ i ] = sum[ i - 1 ] + a[ i ] - k;
        
        int Ans = 0;
        Top = 0; Stk[ ++ Top ] = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( sum[ i ] < sum[ Stk[ Top ] ] ) Stk[ ++ Top ] = i;
        for( int i = n ; i >= 1 ; i -- ) {
            while( Top && sum[ i ] - sum[ Stk[ Top ] ] >= 0 ) Top --;
            Ans = max( Ans , i - Stk[ Top + 1 ] );
        }
        printf("%d ",Ans);
	} 
	return 0;
}

P3503 [POI2010]KLO-Blocks

感谢您的支持，我会继续努力的!